package com.chapter2.sort;

/** 
 * @ClassName: MaxQ 
 * @Description:倒序排列的优先队列(自定义实现)
 * 
 * 二叉堆实现方式
 * 
 * 时间复杂度O(lgN)
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-17 上午3:03:57 
 *  
 */
@SuppressWarnings("unchecked")
public class MaxQ<T extends Comparable<T>>{

	private T[] t;
	
	private int index=0;
	
	private int size=1<<4;
	
	public MaxQ() {
		t=(T[])new Comparable[this.size];
	}

	public void add(T e){
		//在末尾添加元素，并将索引位置+1
		t[++index]=e;
		//上浮
		swiftUp(index);
	}
	
	public T deleteMax(){
		//获取最大元素
		T e=t[1];
		//将末尾元素放到最大元素位置
		t[1]=t[index];
		//删减了一个元素之后，将末尾元素制空
		t[index--]=null;
		//下沉
		swiftDown(1);
		return e;
	}
	
	/**
	 * 
	* @Title: swiftUp 
	* @Description:  上浮
	* @param @param i    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	private void swiftUp(int i){
		while(i>1&&less(i>>1, i)){
			swap(i, i>>1);
			i=i>>1;
		}
	}
	
	/** 
	* @Title: swiftDown 
	* @Description: 下沉 
	* @param @param i    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private void swiftDown(int i) {
		while(i*2<=index){
			int j=i<<1;
			if(less(j, j+1)) j++;
			if(!less(i, j)) break;
			swap(i, j);
			i=j;
		}
	}
	
	/**
	 * 
	* @Title: less 
	* @Description: 大小比较 
	* @param @param i
	* @param @param j
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	private boolean less(int i,int j){
		if(t[j]==null){
			return false;
		}
		return t[i].compareTo(t[j])<0;
	}

	/**
	 * 
	* @Title: swap 
	* @Description: 交换元素位置 
	* @param @param t
	* @param @param a
	* @param @param b    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	private void swap(int a,int b){
		T temp=t[a];
		t[a]=t[b];
		t[b]=temp;
	}
}
